package com.yehui.algorithm.sword;

/**
 * Created by XuChunH on 2016/9/18.
 */
public class FindFirstCommonNode {

    /**
     * 在数据量大时会超时，更好的解法见solution2
     * @param pHead1
     * @param pHead2
     * @return
     */
    public ListNode solution(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        int length1 = length(pHead1);
        int length2 = length(pHead2);
        if (length1 > length2) {
            pHead1 = move(pHead1, length1 - length2);
        } else if (length2 > length1) {
            pHead2 = move(pHead2, length2 - length1);
        }
        while (pHead1 != null && pHead2 != null) {
            if (pHead1.val == pHead2.val) {
                return pHead1;
            }
        }
        return pHead1;
    }

    private int length(ListNode head) {
        if (head == null) {
            return 0;
        }
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }

    private ListNode move(ListNode head, int step) {
        for (int i = 0; i < step && head != null; i++) {
            head = head.next;
        }
        return head;
    }

    public ListNode solution2(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        ListNode temp1 = pHead1;
        ListNode temp2 = pHead2;
        while (temp1 != temp2){
            temp1 = temp1 == null ? pHead2 : temp1.next;
            temp2 = temp2 == null ? pHead1 : temp2.next;
        }
        return temp1;
    }

}
